package Demo55;

/**
 * 重排序链表
 * https://leetcode.cn/problems/reorder-list/description/
 *
 * 解题思路
 * 1. 使用快慢指针, 将链表分半
 * 2. 使用头插法, 将后一半的链表进行逆序
 * 3. 合并两个链表
 */
class Solution {
    /*
        优化后的
     */
    public void reorderList(ListNode head) {
        // 边界值处理
        if(head == null || head.next == null || head.next.next == null) {
            return;
        }
        // 查找到中心节点(使用快慢双指针)
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 使用头插法将slow后的链表逆置
        ListNode head2 = new ListNode(0);
        ListNode cur = slow.next;
        slow.next = null; // 断开两个链表

        while(cur != null) {
            ListNode next = cur.next;
            cur.next = head2.next;
            head2.next = cur;
            cur = next;
        }

        // 合并两个链表
        ListNode cur1 = head;
        ListNode cur2 = head2.next;
        ListNode ret = new ListNode(0);
        while(cur1 != null) {
            // 合并链表1
            ret.next = cur1;
            ret = cur1;
            cur1 = cur1.next;

            if(cur2 != null) {
                ret.next = cur2;
                ret = cur2;
                cur2 = cur2.next;
            }
        }
    }


    /*
        自己第一次
     */
        public void reorderList2 (ListNode head){
            if (head == null || head.next == null) {
                return;
            }

            // 使用快慢指针找到中心点
            ListNode fast = head.next.next; // 快指针
            ListNode slow = head;// 慢指针
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            ListNode node = slow.next;
            slow.next = null;
            // 现在 node 是后一节, head是前一节, 中间已经断开
            // 创建一个新的头节点,然后进行头插法,逆序后面的链表
            slow = new ListNode();
            slow.next = node;
            node = node.next;
            slow.next.next = null;

            while (node != null) {
                ListNode next = node.next;
                node.next = slow.next;
                slow.next = node;
                node = next;
            }
            node = slow.next;

            // 合并两个链表
            ListNode cur1 = head;
            ListNode cur2 = node;
//        while(cur1 != null) {
//            System.out.print(cur1.val + " ");
//            cur1 = cur1.next;
//        }
//        System.out.println();
//        System.out.println("==========");
//        while(cur2 != null) {
//            System.out.print(cur2.val + " ");
//            cur2 = cur2.next;
//        }

            while (cur1.next != null && cur2 != null) {
                ListNode next1 = cur1.next;
                ListNode next2 = cur2.next;
                cur2.next = next1;
                cur1.next = cur2;
                cur1 = next1;
                cur2 = next2;
            }
            if (cur2 != null) {
                cur1.next = cur2;
            }
        }
}
class Demo {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = new int[] {1,2,3,4,5,6,7};
        ListNode head = new ListNode();
        ListNode cur = head;
        for(int a:arr) {
            cur.next = new ListNode(a);
            cur = cur.next;
        }

        solution.reorderList(head.next);
        head = head.next;
        while(head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }
}